//最大子数组和   力扣53
//贪心 局部最优解：从第一个元素开始遍历加和，并记录临时最大值，当加和为负数时
//                 贪心策略为直接舍弃，因为后面的数加上一个负数只会使情况恶化
//                 因此直接舍弃前面的，从下一个元素重新开始计算累加和
class Solution {
public:
	int maxSubArray(vector<int>& nums) {
		int curmax = INT_MIN;//设为最小值
		int cnt = 0; //记录当前的最大值
		for(int i = 0; i < nums.size(); i++)
		{
			cnt += nums[i];
			if(cnt > curmax) curmax = cnt;
			if(cnt < 0) cnt = 0; //若当前数组和小于0，则直接舍弃，从下一个元素开始遍历
		}
		return curmax;
	}
};
